package leetcode.day_2021_03_29_2021_04_04;

/**
 * 81. 搜索旋转排序数组 II
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
 * 未通过
 */
public class LeetCode0081 {

    public static boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left+right) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid]<target && nums[right]>=target) {
                left = mid+1;
            } else if (nums[mid] > target || target >= nums[left]) {
                right = mid-1;
                // 降序
                if (nums[right] <= nums[left]) {
                    int left2 = left;
                    int right2 = right;
                    while (left <= right) {
                        int mid2 = (left+right) / 2;
                        if (nums[mid2] == target) {
                            return true;
                        } else if (nums[mid2] < target) {
                            left2 = mid2+1;
                        }else if (nums[mid2] > target) {
                            right2 = mid2-1;
                        }
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
//        int[] arr = {2,5,6,0,0,1,2};
        int[] arr = {1,0,1,1,1};
        System.out.println(search(arr, 0));
    }
}
